package com.zlk.algorithm.algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName SortTest
 * @description:
 * @author: slfang
 * @create: 2023-12-18 18:52
 * @Version 1.0
 **/
public class SortTest {

    @Test
    public void test1(){
        int testTimes = 100000;
        int maxVal = 200;
        int maxsize = 200;
        for (int i = 0; i < testTimes; i++) {
            int[] randomArr = SortUtils.getRandomArrNoNegative(maxVal, maxsize);
            int[] copy = Arrays.copyOf(randomArr, randomArr.length);
            Arrays.sort(randomArr);
            radixSort(copy);
            if(!SortUtils.isEqual(randomArr,copy)){
                System.out.println("fail");
                System.out.println(Arrays.toString(randomArr));
                System.out.println(Arrays.toString(copy));
                return ;
            }
        }
        System.out.println("success");
    }

    private void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i],max);
        }
        int maxBit = getMaxBit(max);
        int[] help = new int[arr.length];
        for (int d = 1; d <= maxBit; d++) {
            int[] count = new int[10];
            for (int i = 0; i < arr.length; i++) {
                int dbit= getBitByD(arr[i],d);
                count[dbit]++;
            }
            //前准和
            for (int i = 1; i < count.length; i++) {
                count[i] = count[i]+count[i-1];
            }

            for (int i = arr.length-1; i >= 0; i--) {
                int dbit= getBitByD(arr[i],d);
                help[--count[dbit]] = arr[i];
            }

            for (int i = 0; i < arr.length; i++) {
                arr[i] = help[i];
            }
        }

    }

    @Test
    public void test3(){
        System.out.println(getBitByD(1278, 1));
        System.out.println(getBitByD(1278, 2));
        System.out.println(getBitByD(1278, 3));
        System.out.println(getBitByD(1278, 4));
    }

    //  1278   1278
    //
    private int getBitByD(int value, int d) {
        return value/((int)Math.pow(10,d-1))%10;
    }


    private int getMaxBit(int max) {
        int bits = 0;
        /// 1257   125   12  5
        while (max!=0){
            bits++;
            max /=10;
        }
        return bits;
    }


    private void countSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
        }
        int[] bucket = new int[max+1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i]--!=0){
                arr[index++] = i ;
            }
        }

    }


    private void heapSort(int[] arr) {
        int length = arr.length;
//        for (int i = 0; i < length; i++) {
//            heapInsert(arr,i);
//        }
        for (int i = length-1; i >=0 ; i--) {
            heapfiy(arr,i,length);
        }

        int heapSize = length;
        while (heapSize>0){
            SortUtils.swap(arr,0,--heapSize);
            heapfiy(arr,0,heapSize);
        }
    }

    private void heapfiy(int[] arr, int i, int heapSize) {
        int lNode = 2*i+1;
        while (lNode<heapSize){
            int best = lNode+1<heapSize&&arr[lNode+1]>arr[lNode]?lNode+1:lNode;

            best = arr[best]>arr[i]?best:i;
            if(best==i){
                break;
            }
            SortUtils.swap(arr,best,i);
            i = best;
            lNode = 2*i+1;
        }

    }

    private void heapInsert(int[] arr, int i) {
        while (arr[i]>arr[(i-1)/2]){
            SortUtils.swap(arr,i,(i-1)/2);
            i = (i-1)/2;
        }
    }


    private void quickSort(int[] arr) {
        if(arr.length<2||arr==null){
            return ;
        }
        quick(arr,0,arr.length-1);

    }

    private void quick(int[] arr, int l, int r) {
        if(l>=r){
            return ;
        }
        int base = l+(int)(Math.random()*(r-l+1));
        SortUtils.swap(arr,base,r);
        int[] partition = partition(arr, l, r);
        quick(arr,l,partition[0]-1);
        quick(arr,partition[1]+1,r);

    }

    private int[] partition(int[] arr, int l, int r) {
        if(l==r){
            return new int[]{l,l} ;
        }
        if(l>r){
            return new int[]{-1,-1};
        }
        int less = l-1;
        int more = r;
        int index = l;
        while (index<more){
            if(arr[index]<arr[r]){
                SortUtils.swap(arr,index++,++less);
            }else if(arr[index]>arr[r]){
                SortUtils.swap(arr,index,--more);
            }else{
                index++;
            }
        }
        SortUtils.swap(arr,r,more);
        return new int[]{less+1,index};
        //  1  0 2  10 9 2  0  11  12 2
    }


    private void meragesort(int[] arr, int left, int right) {
        if(left==right){
            return ;
        }
        int mid = left+((right-left)>>1);
        meragesort(arr,left,mid);
        meragesort(arr,mid+1,right);
        merage(arr,left,right,mid);
    }

    private void merage(int[] arr, int left, int right, int mid) {
        int[] help = new int[right-left+1];
        int  lIndex = left;
        int  rIndex = mid+1;
        int index = 0;
        while (lIndex<=mid&&rIndex<=right){
            help[index++] = arr[rIndex]<arr[lIndex]?arr[rIndex++]:arr[lIndex++];
        }
        while (lIndex<=mid){
            help[index++] = arr[lIndex++];
        }
        while (rIndex<=right){
            help[index++] = arr[rIndex++];
        }

        //copy
        //int l = left;
        for (int i = 0; i < help.length; i++) {
            arr[left+i] = help[i];
        }
    }


    @Test
    public void test2(){
        int[] arr =new int[]{-5, 4, 5, -4, 2, 2, 8, 9};
        //sort(arr);
    }

    /**
     * @param arr
     */
    private void insertSort(int[] arr) {
        if(arr.length<2||arr==null){
            return ;
        }
        //  1  2  3   2
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j-1>=0&&arr[j]<arr[j-1]){
                SortUtils.swap(arr,j-1,j);
                j--;
            }

        }
    }


    /**
     * 冒泡排序
     * @param arr
     */
    private void bubleSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < arr.length-i; j++) {
                if(arr[j]>arr[j+1]){
                    SortUtils.swap(arr,j,j+1);
                }
            }
        }
    }




    /**
     * 选择排序
     * @param arr
     */
    private void chooseSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length-1; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            SortUtils.swap(arr,i,min);
        }
    }
    //选择排序
}
